package com.algrithom.heap;

import java.util.ArrayList;
import java.util.List;

import org.apache.commons.lang3.StringUtils;

import com.common.constants.NumberConstants;
import com.google.common.collect.Lists;
import com.util.CommonUtil;

/**
 * 堆算法
 * 大顶堆：父节点大于或者等于左右孩子节点 升序
 * 小顶堆：父节点小于或者等于左右孩子节点 降序
 *
 * @author think
 * @version 1.0.0
 * @since 2020/1/13
 */
public class Heap {
    
    private List<Integer> heapList;
    
    public Heap(int capacity){
        heapList = new ArrayList<>(capacity);
    }
    
    public static void main(String[] args){
        int len = 10;
        Heap heap = new Heap(len);
        heap.heapList = Lists.newArrayList(4,99,23,64,25);

        heap.bigHeapSort();
        System.out.println("大堆排序：" + StringUtils.join(heap.heapList,','));

        heap.smallHeapSort();
        System.out.println("小堆排序：" + StringUtils.join(heap.heapList,','));

        heap.buildBigHeap();
        System.out.println("大顶堆：" + StringUtils.join(heap.heapList,','));

        heap.insert(7);
        System.out.println("堆中插入元素后：" + StringUtils.join(heap.heapList,','));

        heap.bigHeapSort();
        System.out.println("大堆排序：" + StringUtils.join(heap.heapList,','));

        heap.removeMax();
        System.out.println("堆中删除元素：" + StringUtils.join(heap.heapList,','));

        heap.bigHeapSort();
        System.out.println("大堆排序：" + StringUtils.join(heap.heapList,','));

        heap.buildSmallHeap();
        System.out.println("小顶堆：" + StringUtils.join(heap.heapList,','));
    }
    
    /**
     * 堆插入元素 从下往上的堆化过程
     *
     * @param data 输入数据
     */
    public void insert(int data){
        heapList.add(data);
        int i = heapList.size();
        while (heapList.get(i - 1) > heapList.get(i / NumberConstants.TWO)) {
            CommonUtil.swap(heapList,i - 1,i / NumberConstants.TWO);
            i = i / NumberConstants.TWO;
        }
    }
    
    /**
     * 移除堆顶数据 从上往下的堆化过程
     */
    public void removeMax(){
        if (heapList.isEmpty()) {
            return;
        }
        heapList.set(0,heapList.get(heapList.size() - 1));
        heapList.remove(heapList.get(heapList.size() - 1));
        adjustBigHeap(heapList.size(),0);
    }
    
    /**
     * 大顶堆
     *
     * @param i 序号
     */
    private void adjustBigHeap(int len,int i){
        int maxPos = i;
        // 根节点小于左孩子
        if (i * NumberConstants.TWO + NumberConstants.ONE < len && heapList.get(i) < heapList.get(i * NumberConstants.TWO + NumberConstants.ONE)) {
            maxPos = i * NumberConstants.TWO + NumberConstants.ONE;
        }
        // 根节点小于右孩子
        if (i * NumberConstants.TWO + NumberConstants.TWO < len && heapList.get(maxPos) < heapList.get(i * NumberConstants.TWO + NumberConstants.TWO)) {
            maxPos = i * NumberConstants.TWO + NumberConstants.TWO;
        }
        // 根节点大于左右孩子
        if (maxPos == i) {
            return;
        }
        // 交换数据
        CommonUtil.swap(heapList,i,maxPos);
        adjustBigHeap(len,maxPos);
    }
    
    /**
     * 大顶堆
     *
     * @param i 序号
     */
    private void adjustSmallHeap(int len,int i){
        int maxPos = i;
        // 根节点小于左孩子
        if (i * NumberConstants.TWO + NumberConstants.ONE < len && heapList.get(i) > heapList.get(i * NumberConstants.TWO + NumberConstants.ONE)) {
            maxPos = i * NumberConstants.TWO + NumberConstants.ONE;
        }
        // 根节点小于右孩子
        if (i * NumberConstants.TWO + NumberConstants.TWO < len && heapList.get(maxPos) > heapList.get(i * NumberConstants.TWO + NumberConstants.TWO)) {
            maxPos = i * NumberConstants.TWO + NumberConstants.TWO;
        }
        // 根节点大于左右孩子
        if (maxPos == i) {
            return;
        }
        // 交换数据
        CommonUtil.swap(heapList,i,maxPos);
        adjustSmallHeap(len,maxPos);
    }
    
    /**
     * 大顶堆
     */
    private void buildBigHeap(){
        int len = heapList.size();
        for (int i = len / NumberConstants.TWO; i >= 0; --i) {
            adjustBigHeap(len,i);
        }
    }
    
    /**
     * 小顶堆
     */
    private void buildSmallHeap(){
        int len = heapList.size();
        for (int i = len / NumberConstants.TWO; i >= 0; --i) {
            adjustSmallHeap(len,i);
        }
    }
    
    public void bigHeapSort(){
        buildSmallHeap();
        int k = heapList.size() - 1;
        while (k > 0) {
            CommonUtil.swap(heapList,0,k);
            adjustSmallHeap(k--,0);
        }
    }
    
    public void smallHeapSort(){
        buildBigHeap();
        int k = heapList.size() - 1;
        while (k > 0) {
            CommonUtil.swap(heapList,0,k);
            adjustBigHeap(k--,0);
        }
    }
}
